The previous slide introduced the Selection Sort mechanism, which guarantees high swap efficiency by performing at most one swap per major pass. We will now trace the algorithm using the array $A = [8, 2, 5, 1, 6]$ (where $n=5$) to visualize how this approach minimizes data movement while maintaining correctness.
- Each pass $i$ locates the absolute minimum element in the remaining unsorted suffix $A[i..n-1]$ by performing $O(n-i)$ comparisons. This confirms that the total number of comparisons is fixed at $O(n^2)$, regardless of the input state.
- The critical efficiency feature is that data movement is minimal: Selection Sort performs a maximum of $n-1$ swaps, achieving an $O(n)$ swap complexity.
- This makes it an excellent choice when moving data (swapping) is significantly more computationally expensive than comparing keys.
- Note that even if the minimum element is already in the correct starting position for the unsorted suffix (as seen in Pass 2 and 3), the swap operation is conditionally skipped, ensuring only necessary exchanges occur.
Trace Summary: A = [8, 2, 5, 1, 6]
| Pass (i) | Unsorted Suffix | Minimum Index Found | Array State (End of Pass) | Cumulative Swaps |
|---|---|---|---|---|
| 0 | [8, 2, 5, 1, 6] | 3 (Value 1) | [1, 2, 5, 8, 6] | 1 |
| 1 | [2, 5, 8, 6] | 1 (Value 2) | [1, 2, 5, 8, 6] | 1 |
| 2 | [5, 8, 6] | 2 (Value 5) | [1, 2, 5, 8, 6] | 1 |
| 3 | [8, 6] | 4 (Value 6) | [1, 2, 5, 6, 8] | 2 |